import java.util.Arrays;

public class Solution1 {
	public int maxValue(int[] w, int[] v, int bag) {
		int N = w.length;
		// maxId[i] 表示重量不超过i的物品中 价值最大的物品的下标
		int[] maxId = new int[100001];
		// secondId[i] 表示重量不超过i的物品中 价值次大的物品的下标
		int[] secondId = new int[100001];
		Arrays.fill(maxId, -1);
		Arrays.fill(secondId, -1);
		int max = bag;
		int min = 100000;
		for (int i = 0; i < N; i++) {
			int curW = w[i];
			maxId[curW] = i;
			max = Math.max(max, curW);
			min = Math.min(min, curW);
		}
		int top1 = 0, top2 = 0;
		int index1 = -1, index2 = -1;
		for (int i = min; i <= max; i++) {
			int curIndex = maxId[i];
			if (curIndex != -1) {
				int curV = v[curIndex];
				if (curV > top1) {
					top2 = top1;
					index2 = index1;
					top1 = curV;
					index1 = curIndex;
				} else if (curV > top2) {
					top2 = curV;
					index2 = curIndex;
				}
			}
			maxId[i] = index1;
			secondId[i] = index2;
		}
		int ans = 0;
		for (int i = 0; i < N; i++) {
			if (w[i] <= bag) {
				int cur = v[i];
				int need = bag - w[i];
				int id = maxId[need] != i ? maxId[need] : secondId[need];
				if (id != -1 && id != i) {
					cur += v[id];
				}
				ans = Math.max(ans, cur);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		int ans = so.maxValue(new int[] { 400, 400, 400 }, new int[] { 300, 200, 100 }, 800);
		System.out.println(ans);
	}
}
